SuperHack/SuperHack CD.bin/CODING/DELPHI/EZDSL200.ZIP/EZDSL.DOC

Text File | 1996-03-13 | 96.9 KB | 2,428 lines

======================================================================
                                EZDSL
                            version 2.00

          Easy classical data structures for Delphi 1 and 2

              Copyright (c) 1993,1996 Julian M. Bucknall
======================================================================


Introduction
----------------------------------------------------------------------

The EZDSL units provide an OOP interface for classical data structures
for Delphi: stacks, queues, lists, binary trees and so forth. For
programmers migrating from BP7 a TCollection replacement is also
provided.

My objective in writing these units was to provide myself with a set
of well-encapsulated classes that would manage the tedium of using
these types of data structures, leaving me to concentrate on coding
my latest program. Having used Borland's TCollection from Turbo
Vision and OWL a great deal, I also wanted to mimic as far as I could
the functionality and naming conventions contained within that
object, without necessarily restricting myself by doing so.

This library was rewritten from my EZSTRUCS library that I first
released in August 1994. It was not a simple port; I was determined to
use some of the whizz new syntax of Delphi: exceptions, virtual
constructors, properties and so on. The first version of EZDSL
appeared in 1995, this later version was ported to 32 bits for the
Delphi 2.0 compiler; of course making sure that it could still be
compiled with Delphi 1.0 in 16 bits.

Within these notes I shall not spend too much time describing how the
data structures work and what they're for; any data structures book
will be able to provide that kind of information easily. The three I
have made a great deal of use of (and that I recommend heartily) are

  Algorithms, by Robert Sedgewick; Addison-Wesley
  Data Structures, Algorithms and Performance, by Derek Wood;
    Addison-Wesley
  Practical Data Structures in C++, by Bryan Flamig; Wiley

Also, the three volumes of The Art of Computer Programming by Knuth
belong on every serious programmer's shelf, although they are
starting to look their age as far as the programming examples go.

Also these units require that you have a fairly good grounding in
using pointers, objects and classes in Delphi, including typecasting.
If you need to, please review your Delphi documentation on how to use
them.


Container classes and Data objects
----------------------------------------------------------------------

The EZDSLxxx units define a set of data object containers. These
are kinds of containers into which you throw a bunch of data 'things'
and retrieve them at a later stage. The data 'things' can be
anything:  integers, strings, records, object instances, or whatever;
we'll use the generic term data object. The different kinds of
containers each have different characteristics, some will keep the
data objects sorted in some order, some will give you fast serial
access times, some will just give you them back in the same order you
put them in.  Some will allow you to navigate through the structure
(and will provide a classic iterator method), some do not.

The containers can be separated into two types: those that own their
data objects, and those that do not. Being a data owner means that a
container will destroy its data objects when it is emptied or itself
destroyed. This distinction means that you could create two skip
lists for example, one a data owner and the other not, each with a
different sort sequence. You could then insert the same set of data
objects into both and know that when you call the Empty method for
both lists, the data objects will get destroyed only once.

As you look at the code for the containers and at this documentation,
you'll see that the hierarchy tree is fairly flat (or narrow if you
look at it vertically):

       TAbstractContainer                 (EZDSLBSE.PAS)
         +--TStack                        (EZDSLSTK.PAS)
         +--TQueue                        (EZDSLQUE.PAS)
         |    +--TDeque                   (EZDSLQUE.PAS)
         +--TPriorityQueue                (EZDSLPQU.PAS)
         +--TLinkList                     (EZDSLLST.PAS)
         +--TDList                        (EZDSLDBL.PAS)
         +--TSkipList                     (EZDSLSKL.PAS)
         +--TBinTree                      (EZDSLBTR.PAS)
         |    +--TBinSearchTree           (EZDSLBTR.PAS)
         |         +--TrbSearchTree       (EZDSLBTR.PAS)
         +--TEZCollection                 (EZDSLCOL.PAS)
              +--TEZSortedCollection      (EZDSLCOL.PAS)
                   +--TEZStringCollection (EZDSLCOL.PAS)
                   +--TEZStrZCollection   (EZDSLCOL.PAS)

There is a single ancestor class that provides the important common
methods and fields (allocating/freeing a node, whether a container is
empty) and the base of the virtual methods hierarchy (Compare,
DisposeData, et al). Most of the other classes are descended directly
from this, with only a few further descendants. This is contrary to
lots of other container hierarchies where the author has endeavoured
to arrange things so that everything descends from one another all the
way back to a doubly linked list or something. I felt that this type
of scheme was too restricting: if I found a better implementation of a
list (and I think it can be done better with TEZCollections for
example) I don't have to worry too much about breaking up my hierarchy
(so long as I interface the same methods). The other thing is that
deriving a stack from a linked list for example means that not only do
you get the Push and Pop methods but you also get a whole slew of
linked list methods appearing as well (Prev, Next, Insert, Delete or
whatever).

However I have tried to be consistent in my naming convention so that
for example, there is a method called Next for a TLinkList, TDList and
TSkipList but it works in different ways for each (and has a different
calling interface) - the Next method is not virtual.

The EZDSL library has been written assuming that the data objects are
pointers to something. Like TCollections from BP7, this makes it easy
to have the containers have lots of different kinds of objects and to
be able to deal with them properly.  However, there is nothing to stop
you using pointers to strings or even plain longints instead; just
typecast to a pointer when required (and typecast back again when the
object is retreived from the container!). For example when using a
stack you could use integers as follows:

  var
    MyStack : TStack;
  begin
    MyStack.Init;
    with MyStack do
      begin
        Push(pointer(19));
        Push(pointer(57));
        writeln(longint(Pop)); {outputs: 57}
        writeln(longint(Pop)); {outputs: 19}
      end;
    MyStack.Done;
  end;

Or you could write a container that would wrap up this slight
awkwardness and hide it from you. See the example programs EXINTQUE
and EXSTRSTK.


Data Objects and Polymorphism
----------------------------------------------------------------------

The first version of the EZSTRUCS unit (on which this library is
based) had virtual methods called Compare, DisposeData and DupData.
However, I found that often the ONLY methods I was overriding were...
Compare, DisposeData and DupData! The data container worked fine 'out
of the box', it was such a pain to override yet another class just to
alter one of these methods.

I had two solutions to my perceived problem: make the data objects
derive from an ancestor object class or make the methods function
pointers.  The first was out (I find it awkward), but the second was
just what I wanted. In fact Delphi itself is rife with this kind of
delegation model.

So, the data object related methods in the containers are in fact
procedure and function pointers held as properties in the container.
You set them when you initialise a new container, and they will be
used whenever two data objects need to be compared, or a data object
needs to be disposed of or you need to duplicate a data object.

To set them you first create your new container object by calling the
Create constructor. This sets the internal procedure and function
pointers of the object to 'do nothing' routines. Then you set the
actual routines you want to use by modifying the required properties:
Compare, DisposeData and DupData.  EZDSL provides the ones used most
often in EZDSLSUP.PAS:  comparison between two longints, between two
strings (short strings in Delphi 2.0), disposing and duplicating the
same.  Please note that it doesn't make any sense to alter these
routines when the container is not empty and so setting these
properties in that case do nothing. In particular you cannot suddenly
change the order of data objects in a sorted container by changing the
Compare property that the container uses.

The Compare, DisposeData and DupData routines that you write *must*
be global, declared 'far' in Delphi 1.0 and declared using the normal
Pascal fastcall calling convention (viz 'register') in Delphi 2.0. In
other words

   (a) they cannot be nested routines;
   (b) in Delphi 1.0 they cannot be declared implicitly or explicitly
       as near routines; and
   (c) in Delphi 2.0 cannot be declared 'cdecl' or 'stdcall'.

They must also follow the routine prototypes TCompareFunc,
TDisposeDataProc and TDupDataFunc respectively.

To facilitate cloning containers with the most flexibility, you can
clone a container and use a different Compare function than the
container you are cloning from (useful for maintaining trees or lists
with their data objects in two different orders).


Sorted Containers, Compare and Duplicate Data Objects
----------------------------------------------------------------------

A number of the containers in EZDSL maintain their data objects in
some kind of ordered sequence. The sequence that they are maintained
in is defined by the container's Compare property.

Some containers are automatically and always 'sorted': skip lists
and binary search trees are two examples. Some are never sorted:
stacks and queues for example. Some containers can be used sorted or
unsorted: examples are linked lists or double linked lists.

The Compare property is a function that you write (or is one of the
supplied functions). The routine must compare two data objects and
return a negative number (eg -1) if the first data object is 'less'
than the second, zero if they are equal, and a positive number (eg 1)
if the first is greater than the second.  As described above you set
a container's Compare property when the container is empty.  The
Compare function is used only by sorted containers or by unsorted
containers that implement a Search method.  Unsorted containers that
do not have a Search method do not use the Compare property, and so in
these cases it does not have to be set.

Once you accept that certain containers maintain data objects in an
ordered sequence, you have to consider the problem of duplicate data
objects. Two data objects are defined as duplicate if the container's
Compare function returns zero when called with them as parameters.
Well, EZDSL enforces a strict rule: sorted containers *cannot*
contain duplicate data objects. All sorted containers will raise an
exception (with string code edsInsertDup) if you attempt to insert a
data object that compares equal to an already inserted data object.

You might have decided that this is a somewhat harsh restriction.
Well, yes and no. Some containers just cannot be used with duplicate
data objects (the skip list is the main example; if you try to, some
wierd effects will occur).  Some containers will internally reorganise
themselves, and will destroy any arrival sequence that duplicate data
objects could have been inserted with (the red-black binary search
tree is the main example here). Rather than document that some
containers will accept duplicate items and some won't and if they did
what kind of wierd effects could happen on deletion and insertion, I
decided to restrict all sorted containers in the same manner: they
will not accept duplicate data objects.

What to do? Suppose you had the kind of use for a skip list that
absolutely had to accept duplicate data objects? Firstly I would ask
you to redesign your data object so that duplicates could not occur
and secondly recode your Compare function so that maybe another field
of the data object could be used in the comparison to remove the
ambiguity.

If all fails, one solution could be to declare a sequence long integer
in your container descendant class. Set this to zero in your
constructor. Make sure that your data objects have a sequence field,
and that your Compare function checks this after your main comparison.
Override the Insert method of the container to increment the
container's sequence field and set the data object's sequence field to
it, and then call the inherited insert method.  This algorithm is
shown in the example program EXINSDUP.

As always with rules, there is one exception to the 'no duplicates'
rule:  the priority queue. This container will accept duplicate data
objects.  However duplicate data objects will *not* be popped off in
arrival sequence or, reverse arrival sequence, or any other
deterministic sequence; as far as the priority queue is concerned
duplicate data objects are exactly that, it cannot distinguish
between them in any way. Again if this matters to you, you'll HAVE to
redefine your data object and Compare function to remove the anomaly.


Nodes and Node Stores
----------------------------------------------------------------------

We all know that these classical data structures are generally
implemented with nodes. For a doubly linked list a node is usually
represented by a structure of the form:

  PMyNode = ^TMyNode;
  TMyNode = record
    Next : PMyNode;     {Link to next node in the chain}
    Prev : PMyNode;     {Link to previous node in the chain}
    Data : SomeRecord;
  end;

When writing the unit I wanted to get away from the dependance of
knowing about this typical node structure: I wanted to insert, push,
examine, delete or pop data objects without having to be continually
reminded of the underlying algorithm. Also, I didn't want to have to
descend my data objects from a TNode object - I would be forced to
always use TNode descendants and couldn't use PStrings or something
along those lines. Also, by divorcing myself from knowing about
(worrying about) the node structure, I was able to make numerous
economies in data storage and speed.

However, some of these data structures cry out for being able to
navigate through the structure. The navigation is performed by the
container class' methods. Sometimes where you are in the
structure is stored internally in the container object (an internal
cursor), sometimes you have explicit 'cursors' to help you move around
the container (external cursors). All containers have methods to move
these internal and external cursors around the object. Of course
stacks and queues and similar structures do not, you can only
reference the topmost object (they are inherently non-navigable).

Also because, the node structure is hidden I was able to implement a
node suballocator scheme (called a TNodeStore; see the source) to
help me and the containers manage blocks of nodes, rather than just
one at a time.  Because the nodes are all the same size for a given
container type (with two exceptions: TSkipList and TEZCollection), we
can take advantage of this and speed up allocations and deallocations
of nodes, compared with using the heap. So if you look at the
TNodeStore code you'll see things like node reuse, several containers
using the same node store and so on.


Iterators
----------------------------------------------------------------------

For the navigable containers (ie those containers where a cursor is
defined) an iterator method is defined. This is called Iterate, and
takes over from the two iterators called ForEach and FirstThat from
olden days; the Iterate method does double duty as will be seen.

Each iterator takes three parameters: an Action routine, a direction
flag and a ExtraData pointer. The ExtraData pointer is simply to
enable you to pass any kind of record structure to the Action
routine: it negates the need for global variables or for a nested
Action routine (c.f.  Borland's TCollection in BP7). The direction
flag (called Backwards) enables you to iterate through the container
from either one of two directions: forwards or backwards.

The Action routine for a ForEach call has to be of the form:

  TIteratorProc = function (C : TAbstractContainer;
                            aData : pointer;
                            ExtraData : pointer) : boolean;

where C will be the container itself, aData is the current data
object and ExtraData is the same extra data pointer you passed to
ForEach. The function must return True to cause the Iterate routine
to continue iterating or False to cause the Iterate routine to stop
(and return the data object that cause the Action routine to return
False).  Remember that your Action procedure CANNOT be a nested
routine (in Delphi 1.0 it must be declared 'far'; in Delphi 2.0 it
must be declared as 'register' (ie the normal fastcall declaration)).

A quick example: suppose your data objects had an integer field called
Value and you wanted to find the sum of all the Value fields in a
list. Your Action procedure would look like:

  function SumValues(C : TAbstractContainer;
                     aData : pointer;
                     ExtraData : pointer) : boolean; far;
    var
      {ExtraData is a pointer to a longint: so typecast it}
      Sum :  ^longint absolute ExtraData;
    begin
      inc(Sum^, PMyObject(aData).Value);
      Result := true;
    end;

and you would call Iterate to do the summation as follows:

  var
    TotalValue : longint;
    MyList : TLinkList;
  begin
    {...}
    TotalValue := 0; {clear the total}
    MyList.Iterate(SumValues, false, @TotalValue);
    {...}
  end.

Notice that the SumValues procedure is explicitly declared 'far' in
Delphi 1.0 (in Delphi 2.0 this modifier is ignored). I have found this
method to be by far (!) the easiest method of ensuring that the Delphi
1.0 compiler will compile my source code without relying on the
current value of the $F compiler define.


Debugging and Errors and Exceptions
----------------------------------------------------------------------

When I started writing this unit I had several goals, but there were
two which seemed incompatible: it had to be fast and it had to have
lots of checks built in to trap any errors that might occur.

This second goal is further complicated because there are broadly two
types of error that could occur: an error due to a programming
mistake and errors due to some run-time problem. This is necessarily
a wishy-washy definition, but generally the run-time problems would
be things like running out of memory whilst adding a data object, and
the programming mistakes would be things like trying to pop a data
object from an empty stack. Another way to view this would be to
define programming mistakes as being those things which would apply
to every machine, whereas the run-time problems would vary from user
to user and from machine to machine. Normal testing should identify
programming mistakes, whereas the other type of error are exceptions
to the norm.

I thought about how I might trap programming mistakes and decided to
use assertion checks as in the C language. An assertion is a simple
debugging routine that checks whether something is true.  If this is
the case the program continues. If it is false, the program is
terminated immediately by writing out a string explaining why (we
shall however be raising an exception).  In C this is accomplished by
the Assert macro.  Compile your C program in one way during testing
and the Assert macro expands to this kind of check; compile it in
another way (for your production app) and the Assert macro 'expands'
to a null statement.  As you see, during testing you have the full
set of checks to aid in debugging (slow but safe), and once you have
fully tested the application you can turn them all off to obtain the
full speed.

Unfortunately in Pascal these kind of preprocessor macros are not
available. I worked round the problem by having a compiler define
called DEBUG which firstly automatically activates the $D+ and $L+
compiler options, and secondly causes a lot of methods to have a call
to Assert at the start of the routine to check that various entry
conditions are met.

An example should make this clear. The TStack object has a method
called Pop to remove the topmost data object from the stack. If the
stack is empty, I count calling Pop as a programming mistake: you
really should check for the stack being empty in your program prior
to calling Pop. Of course Pop could have an if statement within it
that did this check for you, but in the *majority* of cases the stack
won't be empty when Pop is called and in the *majority* of cases when
you use Pop, you'll have some kind of loop in your program which is
continually checking whether the stack is empty or not anyway. In my
mind having a check for an empty stack within Pop is safe but slow.
So, instead, Pop has a call to an Assert procedure at the start
(activated by the DEBUG compiler define) that checks to see whether
the stack is empty. Here is the code for Pop:

      function TStack.Pop : pointer;
        var
          Node : PNode;
        begin
          {$IFDEF DEBUG}
          Assert(not IsEmpty, ascEmptyPop);
          {$ENDIF}
          Node := Head^.Link;
          Head^.Link := Node^.Link;
          Pop := Node^.Data;
          acDisposeNode(Node);
        end;

As you see, if DEBUG is set the Assert procedure checks whether the
stack is empty first, if not it executes the code that pops the data
object off the stack. If the stack is empty an EEZAssertionError
exception is raised (the constant ascEmptyPop is a string code for a
stringtable resource).  If DEBUG is not set the code runs at full
speed.

In the method descriptions below, I will show when an assertion check
(activated with the DEBUG define) has been built into the method's
code. You may assume that if the DEBUG define is off and the
condition that the assertion check test for occurs, very bad things
will happen to your program. These could be as 'benign' as a memory
leak, or as dreadful as a memory overwrite. It is up to you to
thoroughly test your program with the DEBUG define set, before you
turn it off.

The other type of error (that which occurs infrequently and is due to
some 'at the limit' problem) will cause an EEZContainerError
exception to be raised. The strings that the exception class uses are
defined in a stringtable resource (EZDSLCTS.RES, string codes in
EZDSLCTS.PAS), so that you may alter them at will (eg translate them
into another language).

You can rest assured that when exceptions are raised, resources will
be conserved via try..finally blocks. If you also have EZSTRUCS you
might find it amazing how easy try..finally blocks make your code
easier to understand compared with the 'old' method involving flags
and checks for errors all over the place.


Compiler Defines
----------------------------------------------------------------------

At the beginning of every EZDSL source code file are the following
lines:

    {$I EZDSLDEF.INC}
    {---Place any compiler options you require here----------}


    {--------------------------------------------------------}
    {$I EZDSLOPT.INC}

The include file EZDSLDEF.INC contains the compiler defines for the
EZDSL library. These defines are described below. The include file
EZDSLOPT.INC contains the _unchangeable_ compiler options for the
EZDSL library; by unchangeable I mean that if you do change one or two
then EZDSL might still work, but on the other hand it might not. Any
other defines you can change at will, and EZDSL will compile and run.
These changeable options should be placed inside the indicated place.

The DEBUG compiler define has already been mentioned, but there are
also two other compiler defines from EZDSLDEF.INC to consider. Here is
the full list.

DEBUG defines whether the unit will be compiled with debug information
(if on it automatically sets $D+ and $L+, if off these options are set
off) and with assertion checks activated.  It is on by default.

UseTreeRecursion affects binary trees. If the define is activated (as
it is by default) then any binary tree routines that navigate through
the tree will use recursive algorithms to do it. If the define is
deactivated the routines will remove any navigation recursion by
using a TStack (this is known as unrolling the recursion). The pros
and cons are that recursive routines are simple and fast but can use
a lot of internal stack space (and could end up blowing the stack
should your $M directive be small enough in Delphi 1.0), whereas
unrolling the recursion is slower but does not require a lot of
internal stack space, relying instead on the Pascal heap via a TStack
container. It can also be difficult to estimate the amount of stack
space required for a recursive navigation process on a large binary
tree.

SuppressWarnings is a Delphi 2.0 only compiler define. When active (as
it is by default) all warnings that are generated for the code in
EZDSL are suppressed and you won't see them; when inactive the
warnings are shown as normal. I have found the Delphi 2.0 warnings to
be a mixed blessing: they are great at finding those silly but simple
mistakes we all make (eg forgetting to set a function result) but they
can be fooled by moderately complex code. There are several places in
EZDSL where the compiler generates a warning, but which can be shown
to be false. Maybe you'll have fun turning off the SuppressWarnings
define and working out why the compiler is wrong for the warnings that
are then shown.


Of Compilers and Caveats
----------------------------------------------------------------------

I have tested the EZDSL unit with Borland Delphi 1.02 and Borland
Delphi 2.0.

The EZDSL library has grown out of both my own personal work and my
work at TurboPower. If you are familiar with TurboPower products you
may find echoes of TBigCollection in TEZCollection, and the iterator
idea is lifted from Orpheus' sparse array class.  In return the
container classes in Win/Sys for Delphi (written by Kim Kokkonen) take
some of the ideas from EZDSL and move them further. You could say
EZDSL reflects my programming and coding practices, and is hence
somewhat Julian-centric!


Example programs
----------------------------------------------------------------------

To see how to use the EZSTRUCS unit, check out the example units and
test programs in the same archive file.


Programming Documentation
----------------------------------------------------------------------

The next section contains all the documented container classes and
their documented methods and fields. For the underlying undocumented
classes, fields, methods and algorithms see the source code (Use the
Source, Luke!).

It might be beneficial to review the naming convention for the methods
of these containers; it'll also provide a summary of the important
methods to know.

Create  creates a new instance of the container, and prepares it for
        use. You define whether the container is to 'own' its data
        objects or whether it is just holding a reference to them.

Destroy destroys an object instance, releasing all memory used by the
        container including that held by the remaining data objects
        in the container (providing of course that the container owns
        its objects).

Insert  inserts a data object into the container. For some containers
        there might also be other InsertXxxxx methods that insert data
        objects in certain other defined ways. For stacks and queues
        Insert is known as Push or Append.

Delete  unlinks a data object from a container but does not dispose of
        the memory held by the data object. For stacks and queues
        Delete is known as Pop.

Erase   unlinks a data object from a container and also disposes the
        memory held by the object (if the container owns its data
        objects, that is).

Examine returns the data object at the 'current position' of the
        container. Current position is defined in different ways for
        different containers: for a stack or queue it is the head of
        the stack or queue for example.

Empty   empties the container by calling Erase for all data objects.

IsEmpty returns true if there are no data objects in the container.

Iterate calls its action routine for each data object in the
        container.

Clone   creates an exact duplicate of a data container. All the data
        objects within the container are also duplicated if the new
        container is going to be a data owner, else only the pointers
        to the data objects are copied over. Note that an "exact
        lookalike" copy might not be created, a clone of a binary
        search tree might not look the same, even though all the nodes
        are in sorted InOrder sequence.

Join    adds all the data objects in one container to another (in a
        fashion that makes sense according to the container type). The
        emptied container is disposed of.

Split   splits a container into two, moving all the data objects from
        the split point to a newly created container of the same type
        as the first. In this version of EZDSL, Split has not been
        implemented for binary trees.

══════════════════════════════════════════════════════════════════════

Global Types, Constants and Variables
=====================================

const
  ezdsStartOffset = $E2D5;
  escTooManyItems   = ezdsStartOffset+1;
  escInsInvalidHere = ezdsStartOffset+2;
  escDelInvalidHere = ezdsStartOffset+3;
  escInsertDup      = ezdsStartOffset+4;
  escTreeStackError = ezdsStartOffset+5;
  escTreeQueueError = ezdsStartOffset+6;
  escCannotMoveHere = ezdsStartOffset+7;
  escIncompatible   = ezdsStartOffset+8;
  escNoCompare      = ezdsStartOffset+9;
  escNoDupData      = ezdsStartOffset+10;
  escNoDisposeData  = ezdsStartOffset+11;
  escBadSource      = ezdsStartOffset+12;
  ascFreeNilNode    = ezdsStartOffset+20;
  ascNewNodeSize0   = ezdsStartOffset+21;
  ascFreeNodeSize0  = ezdsStartOffset+22;
  ascEmptyExamine   = ezdsStartOffset+23;
  ascEmptyPop       = ezdsStartOffset+24;
  ascDeleteEdges    = ezdsStartOffset+25;
  ascExamineEdges   = ezdsStartOffset+26;
  ascInsertEdges    = ezdsStartOffset+27;
  ascReplaceEdges   = ezdsStartOffset+28;
  ascAlreadyAtEnd   = ezdsStartOffset+29;
  ascAlreadyAtStart = ezdsStartOffset+30;
  ascCannotJoinHere = ezdsStartOffset+31;
  ascCannotJoinData = ezdsStartOffset+32;
  ascSplitEdges     = ezdsStartOffset+33;
  ascOutOfRange     = ezdsStartOffset+34;
  ascExamineLeaf    = ezdsStartOffset+35;
  ascBadSkipLevel   = ezdsStartOffset+36;

Various string constants defining error and assertion conditions.
The strings themselved are held in EZDSLCTS.RES in a stringtable. As
Windows only allows one stringtable per application ezdsStartOffset
can be altered to any constant value so that the string constants
don't clash with your current application.

const
  skMaxLevels = 16;

The maximum number of levels in a skip list. A skip list node will
never have more than this number of forward pointers.

type
  TChild = (CLeft, CRight);

For binary trees: flags for left and right children.

type
  TCompareFunc = function (Data1, Data2 : pointer) : integer;

Function prototype for comparing two data objects. The function must
return a negative number if Data1 is less than Data2, 0 if they are
equal, and a positive number if Data1 is greater than Data2.

type
  TDisposeDataProc = procedure (aData : pointer);

Procedure prototype for disposing a data object.

type
  TDupDataFunc = function (aData : pointer) : pointer;

Function prototype for duplicating data objects. The function must
create a duplicate to the aData data object and return it as the
function result.  If the duplication fails for some reason, then the
function must raise an exception.

type
  TIterator = function  (C : TAbstractContainer; aData : pointer;
                         ExtraData : pointer) : boolean;

Function prototype for an Iterate method iterator. C is the
container whose Iterate method was called. aData is the
current data object.  ExtraData is the extra pointer you passed to
Iterate. The function must return true if Iterate is to continue
iterating, false if Iterate is to stop immediately.

type
  TListCursor = longint;

Navigation cursor for TDList and TSkipList (double linked & skip
lists).

type
  TTraversalType = (ttPreOrder, ttInOrder, ttPostOrder, ttLevelOrder);

For binary trees: the different methods of traversing their nodes.

type
  TTreeCursor = longint;

Navigation cursor for TBinTree and descendants (binary trees).

type
  TEZString = string[255];
  PEZString = ^TEZString;

Essentially for compatibility between Delphi and Delphi 2.0: these
provide a much needed single type for short strings.

──────────────────────────────────────────────────────────────────────

Routines (all within EZDSLSUP.PAS)
========

Declaration
  function  EZIntCompare(Data1, Data2 : pointer) : integer;
Description
  Intended as a compare function for containers: compares two
  longints.

Declaration
  procedure EZIntDisposeData(aData : pointer);
Description
  Intended as a data disposal procedure for containers: disposes a
  longint. In other words, does nothing!

Declaration
  function  EZIntDupData(aData : pointer) : pointer;
Description
  Intended as a data duplication function for containers:  duplicates
  a longint. Essentially it returns aData.

Declaration
  function  EZStrNew(const S : string) : PEZString;
Description
  Allocates a memory block on the heap, copies S to it, and returns
  the pointer to the memory block. Exactly equivalent to NewStr in
  Delphi 1.0. In Delphi 2.0 EZStrNew provides a pointer to a short
  string, not a long string.

Declaration
  procedure EZStrDispose(PS : PEZString);
Description
  Disposes of a string allocated on the heap by EZStrNew.

Declaration
  function  EZStrCompare(Data1, Data2 : pointer) : integer;
Description
  Intended as a compare function for containers: compares two
  strings in case-sensitive manner. The strings are assumed to have
  been assigned with the EZStrNew routine, in other words are short
  strings in Delphi 2.0.

Declaration
  procedure EZStrDisposeData(aData : pointer);
Description
  Intended as a data disposal procedure for containers: disposes a
  string. The string is assumed to have been assigned with the
  EZStrNew routine.

Declaration
  function  EZStrDupData(aData : pointer) : pointer;
Description
  Intended as a data duplication function for containers:  duplicates
  a string. The string is assumed to have been assigned with the
  EZStrNew.

──────────────────────────────────────────────────────────────────────

TAbstractContainer (EZDSLBSE.PAS)
==================

This type is an abstract container class, an ancestor to all the
other containers. Most methods have to be or must be overridden, but
it forms a base object from which more complex objects can be
derived.  Please review the descriptions of the properties defined
below; the most important are Compare, and DisposeData; DupData is
only required if you are going to be cloning containers.

Do *not* create an instance of this object type.

Properties
----------

Declaration
  property Count : longint
Description
  READ ONLY. The number of data objects in the container.

Declaration
  property Compare : TCompareFunc
Description
  The container's Compare function. If you don't 'override' it, the
  default one raises an exception.

Declaration
  property DisposeData : TDisposeDataProc
Description
  The container's DisposeData procedure. If you don't 'override' it,
  the default one raises an exception.

Declaration
  property DupData : TDupDataFunc
Description
  The container's DupData function. If you don't 'override' it, the
  default one raises an exception.

Declaration
  property IsDataOwner : boolean
Description
  READ ONLY. True if the container was created as a data owner, False
  otherwise. It is not possible to change this property after the
  container has been created.


Interfaced methods
------------------

Declaration
  constructor Create(DataOwner : boolean); virtual;
Description
  Creates the object. Descendants must set the NodeSize field before
  calling this as inherited constructor. If non-zero, this method
  gets a pointer to the relevent node store (if zero the descendant
  will be taking care of allocating/freeing nodes).  Sets the
  internal item counter to zero.  The DataOwner parameter determines
  whether the container is to own (ie can dispose of) its data
  objects.

Declaration
  destructor Destroy; override;
Description
  Destroys the container by calling the Empty method, detaches itself
  from the node store.

Declaration
  constructor Clone(Source : TAbstractContainer;
                    DataOwner : boolean; NewCompare : TCompareFunc);
                                                    virtual; abstract;
Description
  Constructor to create a 'clone' (ie an exact copy) of the Source
  container and all its data objects.  Descendants will override this
  constructor without fail. If you are going to use this method you
  *must* override the DupData function as well.  You may specify a
  new Compare function for the cloned container, in which case, if
  the container maintains a sorted order, the new container will have
  its data objects in another order. If DataOwner is true, the new
  container will own its data objects and hence all the objects in
  the original container will be duplicated.

Declaration
  procedure Empty; virtual; abstract;
Description
  Abstract method that empties the container; each container
  descendant will have its own preferred efficient method of doing
  this. NOTE: DisposeData will be called for all objects in the
  container if the container owns its data objects.

Declaration
  function IsEmpty : boolean;
Description
  Returns true if the container is empty; ie it contains no data
  objects.


──────────────────────────────────────────────────────────────────────

TStack (EZDSLSTK.PAS)
======

A stack is a LIFO container (last in first out): the last data object
pushed on will be the first to be popped off. You can also examine
(peek at) the next item to be popped off. However you cannot navigate
through the stack, the data objects underneath the top one are hidden
from you until you pop the ones above off.

Interfaced Methods
------------------

Declaration
  constructor Create(DataOwner : boolean); override;
Description
  Creates the stack by calling the ancestor's Create after setting a
  node size of 8.  If DataOwner is true, the new stack will own its
  data objects.

Declaration
  constructor Clone(Source : TAbstractContainer;
                    DataOwner : boolean; NewCompare : TCompareFunc);
                                                            override;
Description
  Creates a copy of a Source stack.

Declaration
  procedure Empty; override;
Description
  Repeatedly calls the Pop method (disposing of the data object
  returned if a data owner) until the stack is empty.

Declaration
  function Examine : pointer;
Description
  Returns the data object at the top of the stack without popping it.
  If the stack is empty, nil is returned.

Declaration
  function Pop : pointer;
Description
  Pops the data object from the top of the stack and returns it.  In
  DEBUG mode, an assertion error will occur if the stack is empty.

Declaration
  procedure Push(aData : pointer);
Description
  Pushes the data object aData onto the top of the stack.

──────────────────────────────────────────────────────────────────────

TQueue (EZDSLQUE.PAS)
======

A queue is a FIFO container (first in first out): the first object put
in the queue will be the first popped, the last object will be the
last to be popped. You can examine (peek at) the next data object to
be popped.  However you cannot navigate through the queue.

Interfaced Methods
------------------

Declaration
  constructor Create(DataOwner : boolean); override;
Description
  Creates the queue by calling the ancestor's Create after setting a
  node size of 8.  If DataOwner is true, the new queue will own its
  data objects.

Declaration
  procedure Append(aData : pointer);
Description
  Adds the data object aData to the end of the queue.

Declaration
  constructor Clone(Source : TAbstractContainer;
                    DataOwner : boolean; NewCompare : TCompareFunc);
                                                            override;
Description
  Creates a copy of the Source queue.

Declaration
  procedure Empty; override;
Description
  Repeatedly calls the Pop method (disposing of the data object
  returned if a data owner) until the queue is empty.

Declaration
  function Examine : pointer;
Description
  Returns the data from the top of the queue without popping it. If
  the stack is empty, nil is returned without causing an error.

Declaration
  function Pop : pointer;
Description
  Pops the data object from the front of the queue and returns it.
  In DEBUG mode, an assertion error will occur if the queue is empty.

──────────────────────────────────────────────────────────────────────

TDeque
======

A deque (sometimes pronounced DECK, sometimes DEQUEUE) is a queue
that allows objects to be added to, or removed from the front or back
of the queue. This particular implementation of a deque just allows
queue jumpers, ie data objects can also be pushed into the front of
the queue, giving it stack-like behaviour (Flamig calls this variant
a Staque, see references). It is descended from the basic TQueue and
inherits Pop and Append.

Interfaced Methods
------------------

Declaration
  procedure Push(aData : pointer);
Description
  Pushes the data object aData to the front of the deque.

──────────────────────────────────────────────────────────────────────

TPriorityQueue
==============

A priority queue is much like an ordinary queue, except that the
smallest data object in the queue will be popped first (rather than
the 'oldest'). Another name for a priority queue is a heap (not to be
confused with the Pascal heap where memory blocks are allocated and
freed).  As it imposes a sort order on the data objects, you must
override the Compare function.

If the Compare method returns values in the 'normal' sense (ie
Compare returns a negative number if Data1 < Data2, 0 if Data1 =
Data2, and a positive number otherwise), then data objects will be
popped off smallest first, ie in increasing order. However, if
Compare returns values in the 'reverse' sense (ie returning negative
if Data1 > Data2, etc), then elements will be popped off largest
first, ie in decreasing order. Thus by carefully selecting Compare,
this object will provide the classic min-heap and max-heap data
structures.

Notice that the well-known Heap Sort algorithm uses a structure of
this type, and in fact this structure could be used to provide a
generic sort routine. It will be faster than using a skip list for
example (the data objects are not held internally in a fully sorted
manner, they are just sorted in a 'loose' sense).

Interfaced Methods
------------------

Declaration
  constructor Create(DataOwner : boolean);
Description
  Creates the queue by calling the ancestor's Create after setting a
  node size of 16.  If DataOwner is true, the new queue will own its
  data objects.

Declaration
  procedure Append(aData : pointer);
Description
  Adds the data object aData to the priority queue.

Declaration
  constructor Clone(Source : TAbstractContainer;
                    DataOwner : boolean; NewCompare : TCompareFunc);
                                                            override;
Description
  Creates a copy of the Source queue.

Declaration
  procedure Empty; override;
Description
  Repeatedly calls the Pop method (disposing of the data object
  returned if a data owner) until the queue is empty.

Declaration
  function Examine : pointer;
Description
  Returns the data object from the top of the queue without popping
  it. If the queue is empty, nil is returned.

Declaration
  function Pop : pointer;
Description
  Pops the data object from the front of the queue and returns it.
  If Compare works in the 'normal' sense (ie returns a negative value
  for 'less than') then the data object will be the smallest,
  otherwise the data object will be the largest.  In DEBUG mode, an
  assertion error will occur if the queue is empty.

Declaration
  function Replace(aData : pointer) : pointer;
Description
  Equivalent to an Append followed by a Pop, but faster. Note that
  the same data object could be returned (it maybe smaller (larger)
  than all the data objects in the queue).

──────────────────────────────────────────────────────────────────────

TLinkList
=========

A linked list is a container which is a chain of data objects. From a
given position in the list you can move forwards or backwards to the
next or previous data object. You cannot directly jump to the Nth
data object, instead you have to walk the list from the beginning
counting as you go. This list implementation has an implied 'cursor'
which points to the current data object, you move this cursor along
the list by means of the list's methods (eg Next and Prev). You can
examine the data object that the cursor is pointing to, or insert a
new one before or after the cursor, or delete the data object at the
cursor (unlink it).

There are two special cursor positions associated with this list:
before the first data object (known as BeforeFirst) and after the
last data object (known as AfterLast). Even in an empty list these
are deemed different. In the diagram of a linked list below the three
data objects are a, b and c, and the internal cursor is pointing at
c:

       BeforeFirst --> a --> b --> c --> AfterLast

                                   |
       Cursor ---------------------+


As a convenience to the programmer, this implementation of a linked
list allows the data objects to be maintained in a sorted order. To
do this there are some practical and some theoretical considerations.
The practical ones first: you must override Compare and you must use
InsertSorted to insert data objects into the list. The theoretical
considerations are to do with the linear sequential nature of a
linked list: to find where to insert a data object the list must
start at the beginning of the list and walk the list calling Compare
for each data object it encounters until it finds the place where the
new data object can be inserted. A time-consuming process as you can
appreciate.  You should only use sorted linked lists if the list is
built only once or if the number of data objects in the list is
likely to be small.

This particular implementation is a singly-linked list (each node has
just a single link to the 'next' node), however it uses a particular
algorithm that enables it to have the performance capabilities of a
doubly-linked list (see below) without the overhead of the extra
links.

Properties
----------

Declaration
  property IsSorted : boolean
Description
  READ ONLY. IsSorted is true if the list is currently sorted (ie all
  inserts have been made with InsertSorted, or the list is empty).
  Note that to maintain data objects in sorted order you must supply
  an overridden Compare function and use the InsertSorted method;
  perhaps more importantly keeping a linked list in sorted order
  through many Inserts and Deletes is very inefficient, because of
  the sequential nature of the list.

Interfaced Methods
------------------

Declaration
  constructor Create(DataOwner : boolean);
Description
  Creates the object by calling the ancestor's Create after setting a
  node size of 8.  If DataOwner is true, the new list will own its
  data objects.

Declaration
  constructor Clone(Source : TAbstractContainer;
                    DataOwner : boolean; NewCompare : TCompareFunc);
                                                            override;
Description
  Creates a copy of the Source list. If the original list was sorted
  then the cloned list is also sorted.

Declaration
  procedure Delete;
Description
  Unlinks the current data object but does not dispose of it. The
  internal cursor is moved to the next data object in the list, or to
  the AfterLast position if there are no more objects after it.  In
  DEBUG mode, an assertion error will occur if the cursor is at
  BeforeFirst or AfterLast.

Declaration
  procedure Empty; override;
Description
  Walks the list, calling Erase for every data object it finds.

Declaration
  procedure Erase;
Description
  Works like Delete, but also disposes the data object by calling
  DisposeData if the list owns its data objects.

Declaration
  function Examine : pointer;
Description
  Returns the data object the cursor is pointing to.  In DEBUG mode,
  an assertion error will occur if the cursor is at BeforeFirst or
  AfterLast.

Declaration
  function Iterate(Action : TIterator;
                   Backwards : boolean;
                   ExtraData : pointer) : pointer;
Description
  Walks the list from the start (if Backwards is False) or from the
  end (if Backwards is True) and calls Action for each data object
  found.  If Action returns False for a data object, then Iterate
  immediately returns with that data object; if Action always returns
  True then this method will return nil.  ExtraData is a pointer to
  any other data that you may want Action to use.

Declaration
  procedure InsertAfter(aData : pointer);
Description
  Inserts the data object aData after the cursor. If the list is
  currently sorted, calling this method forces it to an unsorted
  state. Use InsertSorted to maintain a sorted list. In DEBUG mode,
  an assertion error will occur if the cursor is at AfterLast.

Declaration
  procedure InsertBefore(aData : pointer);
Description
  Inserts the data object aData before the cursor. If the list is
  currently sorted, calling this method forces it to an unsorted
  state. Use InsertSorted to maintain a sorted list. In DEBUG mode,
  an assertion error will occur if the cursor is at BeforeFirst.

Declaration
  procedure InsertSorted(aData : pointer);
Description
  Inserts the data object aData in the correct place in the list's
  sequence. Only works if ALL data objects are so inserted; if the
  list is currently unsorted InsertBefore or InsertAfter is called
  instead.  Requires Compare to be overridden. *Not* efficient for
  long lists, you should use a skip list or binary search tree
  instead.

Declaration
  function IsAfterLast : boolean;
Description
  Returns true if the cursor is after all data objects in the list
  (beyond the end of the list).

Declaration
  function IsBeforeFirst : boolean;
Description
  Returns true if the cursor is before all data objects in the list.

Declaration
  procedure Join(List : TLinkList);
Description
  Adds all the data objects in List to the current list, placing them
  after the cursor. List is then destroyed. To add the data objects
  before all the current ones, call SetBeforeFirst first; to add them
  after all the current ones, call SetAfterLast and Prev first. Note
  that if the destination list is sorted, the nodes from List are
  added in sorted order. In DEBUG mode, an assertion error will occur
  if the cursor is at AfterLast.  Please note that both lists
  concerned must either be data owners or not.  You cannot Join a
  list that is a data owner to one that is not.

Declaration
  procedure Next;
Description
  Moves the cursor to the next data object in the list. In DEBUG
  mode, an assertion error will occur if the cursor is at AfterLast.

Declaration
  procedure Prev;
Description
  Moves the cursor to the previous data object in the list. In DEBUG
  mode, an assertion error will occur if the cursor is at
  BeforeFirst.

Declaration
  function Replace(aData : pointer) : pointer;
Description
  Replaces the data object at the cursor with aData and returns the
  replaced data object. Note that for sorted lists, the cursor might
  be moved. In DEBUG mode an assertion error will occur if the cursor
  is currently at BeforeFirst or AfterLast.

Declaration
  function Search(aData : pointer) : boolean;
Description
  Returns true if the data object aData is found in the list (Compare
  must return 0 between it and one of the data objects in the list),
  if not (and the list is sorted) it leaves the cursor just past
  where the data object could be inserted.

Declaration
  procedure SetAfterLast;
Description
  Moves the cursor after all the data objects in the list. Calling
  Prev from this position gives you the last object on the list.

Declaration
  procedure SetBeforeFirst;
Description
  Moves the cursor before all the data objects in the list. Calling
  Next from this position gives you the first object on the list.

Declaration
  function Split : TLinkList;
Description
  Splits the linked list into two at the cursor by creating a new
  list, and moving all the data objects from the cursor onwards to
  the new list. In DEBUG mode, an assertion error will occur if the
  cursor is at BeforeFirst or AfterLast (ie at least ONE data object
  must be moved; you cannot call Split for an empty list).

──────────────────────────────────────────────────────────────────────

TDList
======

This is a linked list of data objects. Compared with TLinkList, this
implementation uses external 'cursors' which point to the various
data objects, you move these cursors along the list by means of the
list's methods. You can examine the data object that a cursor is
pointing to, or insert a new one before or after a given cursor, or
delete the data object at a cursor (unlink it). Again, there are two
special cursor positions: before the first data object (BeforeFirst)
and after the last data object (AfterLast). Even in an empty list
these are different.

The difference between this object and TList is in the use of
external cursors, and also in the internal implementation. This
object uses nodes with two links (hence 'doubly linked') rather than
one.

Notice that it is up to you to make sure that your external cursors
are valid. The following code is deemed a programming error:

  begin
    {...}
    with MyDList do
      begin
        Cursor := Next(SetBeforeFirst);
        NextCursor := Delete(Cursor);
        if (Next(Cursor) = NextCursor) then   {<=== CRASH}
          {...}

Here, the value of Cursor is undefined after the call to Delete. This
is much the same as using pointers: you may have several copies of a
pointer to a heap memory block, but as soon as you free that memory
block all those pointer variables are invalid.

As a convenience to the programmer, this implementation of a doubly
linked list allows the data objects to be maintained in a sorted
order, much as for TLinkList. Please see the discussion of sorted
lists above in that section.

Properties
----------

Declaration
  property IsSorted : boolean
Description
  READ ONLY. Is true if the list is currently sorted (ie all inserts
  have been made with InsertSorted, or the list is empty).

Interfaced Methods
------------------

Declaration
  constructor Create(DataOwner : boolean);
Description
  Creates the object by calling the ancestor's Create after setting a
  node size of 12.  If DataOwner is true, the new list will own its
  data objects.

Declaration
  constructor Clone(Source : TAbstractContainer;
                    DataOwner : boolean; NewCompare : TCompareFunc);
                                                            override;
Description
  Creates a exact copy of the Source list. If the original list was
  sorted then the cloned list is also sorted.

Declaration
  function Delete(Cursor : TListCursor) : TListCursor;
Description
  Unlinks the passed cursor but does not dispose of its data object.
  The cursor of the next data object in the list is returned. Please
  note that the parameter Cursor is invalid after this routine is
  called. In DEBUG mode, an assertion error will occur if Cursor is
  at BeforeFirst or AfterLast.

Declaration
  procedure Empty; override;
Description
  Walks the list, calling Erase for every data object it finds.

Declaration
  function Erase(Cursor : TListCursor) : TListCursor;
Description
  Works like Delete, but also disposes the data object by calling
  DisposeData, providing the list owns its data objects.

Declaration
  function Examine(Cursor : TListCursor) : pointer;
Description
  Returns the data object the cursor is pointing to. In DEBUG mode,
  an assertion error will occur if Cursor is at BeforeFirst or
  AfterLast.

Declaration
  function Iterate(Action : TIteratorFunc;
                   Backwards : boolean;
                   ExtraData : pointer) : TListCursor;
Description
  Walks the list from the first data object (if Backwards is False)
  or from the last data object (if Backwards is True) and calls
  Action for each data object found.  If Action returns False, then
  this method immediately returns with that data object's cursor; if
  Action always returns True then this method will return 0.
  ExtraData is a pointer to any other data that you may want Action
  to use.

Description
  procedure InsertAfter(Cursor : TListCursor; aData : pointer);
Description
  Inserts the data object aData after Cursor. If the list is
  currently sorted, calling this method forces it to an unsorted
  state. Use InsertSorted to maintain a sorted list. In DEBUG mode,
  an assertion error will occur if the cursor is at AfterLast.

Declaration
  procedure InsertBefore(Cursor : TListCursor; aData : pointer);
Description
  Inserts the data object aData after Cursor. If the list is
  currently sorted, calling this method forces it to an unsorted
  state. Use InsertSorted to maintain a sorted list. In DEBUG mode,
  an assertion error will occur if the cursor is at AfterLast.

Declaration
  procedure InsertSorted(aData : pointer);
Description
  Inserts the data object aData in the correct place in the list's
  sequence. Only works if ALL data objects are so inserted; if the
  list is currently unsorted the data object is inserted at the front
  of the list. Requires Compare to be overridden. *Not* efficient for
  long lists, you should use a skip list or binary search tree
  instead.

Declaration
  function IsAfterLast(Cursor : TListCursor) : boolean;
Description
  Returns true if Cursor is after all data objects in the list.

Declaration
  function IsBeforeFirst(Cursor : TListCursor) : boolean;
Description
  Returns true if Cursor is before all data objects in the list.

Declaration
  procedure Join(Cursor : TListCursor; List : TDList);
Description
  Adds all the data objects in List to the current list, placing them
  after Cursor. List is then destroyed. To add the data objects
  before all the current ones, use SetBeforeFirst as cursor; to add
  them after all the current ones, use SetAfterLast and Prev as
  cursor.  Note that if the destination list is sorted, the nodes
  from List are added in sorted order. In DEBUG mode, an assertion
  error will occur if the cursor is at AfterLast.  Please note that
  both lists concerned must either be data owners or not.  You cannot
  Join a list that is a data owner to one that is not.

Declaration
  function Next(Cursor : TListCursor) : TListCursor;
Description
  Given a Cursor into the list, returns a cursor to the next data
  object. In DEBUG mode, an assertion error will occur if Cursor is
  at AfterLast.

Declaration
  function Prev(Cursor : TListCursor) : TListCursor;
Description
  Given a Cursor into the list, returns a cursor to the previous data
  object. In DEBUG mode, an assertion error will occur if Cursor is
  at BeforeFirst.

Declaration
  function Replace(Cursor : TListCursor; aData : pointer) :  pointer;
Description
  Replaces the data object at Cursor with aData and returns the
  replaced data object. In DEBUG mode an assertion error will occur if
  the cursor is currently at BeforeFirst or AfterLast.

Declaration
  function Search(var Cursor : TListCursor;
                      aData  : pointer) : boolean;
Description
  Returns true if the data object aData is found in the list (Compare
  must return 0 between it and an object in the list), and returns
  the cursor. If the data object was not found in a sorted list,
  Search returns the cursor just past where the data object should be
  inserted.

Declaration
  function SetAfterLast : TListCursor;
Description
  Returns the cursor that is after all the data objects in the list.

Declaration
  function SetBeforeFirst : TListCursor;
Description
  Returns the cursor that is before all the data objects in the list.

Declaration
  function Split(Cursor : TListCursor) : TDList;
Description
  Splits the linked list into two at Cursor by creating a new list,
  and moving all the data objects from Cursor onwards to the new list.
  In DEBUG mode, an assertion error will occur if Cursor is at
  BeforeFirst or AfterLast (ie at least ONE data object must be moved;
  you cannot call Split for an empty list).

──────────────────────────────────────────────────────────────────────

TSkipList
=========

A skip list is a special type of linked list of data objects. The
list is sorted and therefore requires the Compare method to be
overridden.  Compared with TList and TDList, this implementation uses
nodes of varying sizes. The nodes have between 1 and 16 (skMaxLevels)
of forward pointers, the higher ones skipping over nodes with less
forward pointers. This means much faster search times, but slightly
slower list update times (ie insert and delete). Can cope with
searching long lists without too much degradation. Compared with a
red-black binary search tree, this type of data structure will
consume more memory, will have equivalent insert times and delete
times, and will have comparable (amortised) search times.

Like TList and TDList, the skip list has two special positions:
before all the data objects and after all the data objects.

To grasp how it works, start with a classic doubly linked list where
each node has a pointer to the next and previous nodes. Now imagine
that about one in four of these nodes has a pointer to the node 4
nodes ahead as well. Furthermore suppose that about one in sixteen of
the nodes has a pointer to the node 16 nodes ahead. And so on. As you
can see, you can navigate through the list pretty quickly, jumping
over lesser nodes and 'homing in' on the node you want. For example,
in the diagram below, to get to g quickly from BeforeFirst, you can
jump to d straightaway, followed by a smaller jump to f followed by a
small jump to g.

              -------------------------------------------->
              -------------------->   -------------------->
              -------->   -------->   -------->   -------->
  BeforeFirst --> a --> b --> c --> d --> e --> f --> g --> AfterLast


Interfaced Methods
------------------

Declaration
  constructor Create(DataOwner : boolean);
Description
  Creates the object by calling the ancestor's Create after setting a
  node size of 0. This means that this object class will do its own
  allocating of nodes; the nodes are of varying sizes from 16 bytes
  to 76 bytes in 16 bit mode (from 20 to 80 bytes in 32-bit mode). If
  DataOwner is true, the new list will own its data objects.

Declaration
  constructor Clone(Source : TAbstractContainer;
                    DataOwner : boolean; NewCompare : TCompareFunc);
                                                            override;
Description
  Creates a copy of the Source skip list.

Declaration
  function Delete(Cursor : TListCursor) : TListCursor;
Description
  Unlinks the passed cursor but does not dispose of its data object.
  The cursor of the next data object in the list is returned. Please
  note that if there are several data objects that Compare equal to
  the data object at Cursor, the *first* of these will be deleted,
  not necessarily the one at Cursor.  Also note that the parameter
  Cursor is invalid after this routine is called. In DEBUG mode, an
  assertion error will occur if Cursor is at BeforeFirst or
  AfterLast.

Declaration
  procedure Empty; override;
Description
  Walks the list, calling Erase for every data object it finds.

Declaration
  function Erase(Cursor : TListCursor) : TListCursor;
Description
  Works like Delete, but also disposes the data object by calling
  DisposeData, providing the list owns its data objects.

Declaration
  function Examine(Cursor : TListCursor) : pointer;
Description
  Returns the data object the cursor is pointing to. In DEBUG mode,
  an assertion error will occur if Cursor is at BeforeFirst or
  AfterLast.

Declaration
  function Iterate(Action : TIteratorFunc;
                   Backwards : boolean;
                   ExtraData : pointer) : TListCursor;
Description
  Walks the list from the first data object (if Backwards is False)
  or from the last data object (if Backwards is True) and calls
  Action for each data object found.  If Action returns False, then
  this method immediately returns with that data object's cursor; if
  Action always returns True then this method will return 0.
  ExtraData is a pointer to any other data that you may want Action
  to use.

Declaration
  procedure Insert(var Cursor : TListCursor; aData : pointer);
Description
  Inserts the data object aData in the correct place in the list's
  sort sequence. Requires Compare to be overridden.

Declaration
  function IsAfterLast(Cursor : TListCursor) : boolean;
Description
  Returns true if the cursor is after all data objects in the list.

Declaration
  function IsBeforeFirst(Cursor : TListCursor) : boolean;
Description
  Returns true if the cursor is before all data objects in the list.

Declaration
  procedure Join(List : TSkipList);
Description
  Adds all the data objects in List to the current list, placing them
  in the correct order. List is then destroyed.  Please note that
  both lists concerned must either be data owners or not.  You cannot
  Join a list that is a data owner to one that is not.

Declaration
  function Next(Cursor : TListCursor) : TListCursor;
Description
  Given a Cursor into the list, returns a cursor to the next data
  object. In DEBUG mode, an assertion error will occur if Cursor is
  at AfterLast.

Declaration
  function Prev(Cursor : TListCursor) : TListCursor;
Description
  Given a Cursor into the list, returns a cursor to the previous data
  object. In DEBUG mode, an assertion error will occur if Cursor is
  at BeforeFirst.

Declaration
  function Replace(Cursor : TListCursor; aData : pointer) : pointer;
Description
  Replaces the data object at the cursor with aData and returns the
  replaced data object. Note that because this is a sorted list, this
  is equivalent to Delete followed by Insert (and is coded that way)
  and Cursor may not be pointing to the same data object afterwards.

Declaration
  function Search(var Cursor : TListCursor; aData : pointer)
                                                            : boolean;
Description
  Returns true if the data object aData is found in the list (Compare
  must return 0 between it and an object in the list), and returns the
  cursor. If the data object was not found in a sorted list, Search
  returns the cursor just past where the data object should be
  inserted.

Declaration
  function SetAfterLast : TListCursor;
Description
  Returns the cursor that is after all the data objects in the list.

Declaration
  function SetBeforeFirst : TListCursor;
Description
  Returns the cursor that is before all the data objects in the list.

Declaration
  function Split(Cursor : TListCursor) : TSkipList;
Description
  Splits the linked list into two at Cursor by creating a new list,
  and moving all the data objects from Cursor onwards to the new list.
  In DEBUG mode, an assertion error will occur if Cursor is at
  BeforeFirst or AfterLast (ie at least ONE data object must be moved;
  you cannot call Split for an empty list).

──────────────────────────────────────────────────────────────────────

TBinTree
========

A binary tree is a data structure that can best be described in a
recursive manner: a tree is either empty or consists of a node with
links to two other trees. Classically a binary tree is drawn:

                         Root
                        /    \
                       a      b
                      / \    / \
                     c   d  e   f

The node at the top of the tree is called the root node. The
implementation of a binary tree in EZSTRUCS uses the concepts of
internal and external nodes. An internal node of the tree always has
two children, an external node (also known as a leaf) has no
children. An external node carries no data object, only internal
nodes can be associated with data objects; if you like, external nodes
are like earth connections in electrical diagrams (in this
implementation external nodes are nil).  In the literature internal
nodes tend to be drawn with small circles and external nodes with
small squares.  In the example above Root, a and b are all internal
nodes; c, d, e, and f are external nodes.  Internal and external
nodes are important when you are inserting or deleting data objects.

Rule 1: you can only insert a data object at an external node. What
happens is that a new internal node is created for the data object
(it is created with two external children), and is placed at the
position occupied by the external node. Think of an internal node
having no 'room' for a new inserted data object. A sorted tree (for
example TBinSearchTree below) has enough information to be able to
restructure the tree (maintaining its essential sorted property) to
violate this rule if it needs to (but in fact it doesn't).

For example inserting NewObject at Leaf below:

       Parent                       Parent
      /      \         ====>       /      \
   Subtree    Leaf              Subtree    NewObject
     |                            |       /         \
    ...                          ...    Leaf       Leaf

Rule 2: you can only delete a node that's (a) internal and (b) has at
least one external child. When you delete the node the external
child(ren) are automatically deleted as well. The reason for this
rule is to allow the tree to remain connected after the deletion.
Again the sorted trees that descend from this object class will know
how to restructure the tree to allow deletion of an internal node
with two internal children. There are two cases to consider.  First
deleting a node with two external children:

       Parent                       Parent
      /      \                     /      \
   Subtree    Node     ====>    Subtree   Leaf
     |        /  \                |
    ...     Leaf Leaf            ...

And second, deleting a node with a single external child (and hence a
single internal child):

       Parent                           Parent
      /      \                         /      \
  Subtree1    Node        ====>    Subtree1    Subtree2
    |        /    \                  |            |
   ...    Leaf   Subtree2           ...          ...
                    |
                   ...

Generally you should only be concerned with this if you are going to
be creating an unsorted binary tree; to reiterate, the sorted variants
will restructure the tree using the sorted property to allow insertion
and deletion at any point.

Trees can be traversed in many different ways; the methods supported
by TBinTree are pre order, in order, post order and level order
traversal, from left to right and vice versa. The definitions of the
first three of these (from left to right), like that of a binary
tree, are recursive:

 PreOrder:  visit the root node, traverse the left sub-tree, traverse
            the right sub-tree. In the first diagram above, nodes
            would be visited in the order Root, a, c, d, b, e, f.

 InOrder:   traverse the left sub-tree, visit the root node, traverse
            the right sub-tree. In the first diagram above, nodes
            would be visited in the order c, a, d, Root, e, b, f.

 PostOrder: traverse the left sub-tree, traverse the right sub-tree,
            visit the root node. In the first diagram above, nodes
            would be visited in the order c, d, a, e, f, b, Root.

The last (LevelOrder) means visiting the root node first, then the
root node of its left subtree, then the root node of its right
subtree, then the root node of its left subtree's left subtree, and
so on, visiting all of the nodes from top to bottom from left to
right at each level. In the first diagram above, nodes would be
visited in the order Root, a, b, c, d, e, f.

When traversing the tree from right to left the definitions are the
same, except that the visiting order is reversed: you will be
visiting the right subtree before the left subtree.


Properties
----------

Declaration
  property TraversalType : TTraversalType
Description
  The traversal type for the Iterate method. Note that you shouldn't
  alter this property in the middle of a call to the Iterate method
  (in the Action function for example).


Interfaced Methods
------------------

Declaration
  constructor Create(DataOwner : boolean);
Description
  Creates the tree by calling the ancestor's Create after setting a
  node size of 16. The initial traversal order for the Iterate method
  is set to InOrder.  If DataOwner is true, the new tree will own its
  data objects.

Declaration
  constructor Clone(Source : TAbstractContainer;
                    DataOwner : boolean; NewCompare : TCompareFunc);
                                                            override;
Description
  Creates a copy of the Source binary tree.

Declaration
  function Delete(Cursor : TTreeCursor) : TTreeCursor; virtual;
Description
  Unlinks the passed cursor from the tree but does not dispose of its
  data object.  The cursor of the data object replacing it in the tree
  is returned. Please note that the parameter Cursor is invalid after
  this routine is called. In DEBUG mode, an assertion error will occur
  if Cursor does not have at least one external child, or if Cursor is
  an external node.

Declaration
  procedure Empty; override;
Description
  Destroys all nodes and data objects in the tree. Does a post order
  traversal of the tree calling Erase for all nodes.

Declaration
  function Erase(Cursor : TTreeCursor) : TTreeCursor;
Description
  Works like Delete except that the data object pointed to by Cursor
  is disposed of as well, providing that the tree owns its data
  objects.

Declaration
  function Examine(Cursor : TTreeCursor) : pointer;
Description
  Returns the data object at Cursor. In DEBUG mode, an assertion error
  will occur if Cursor is an external node (which have no data objects
  associated with them).

Declaration
  procedure Insert(var Cursor : TTreeCursor; aData : pointer);
                                                              virtual;
Description
  Inserts the data object aData into the tree at Cursor, where Cursor
  is assumed to be an external node. In DEBUG mode an assertion error
  will occur if it is not.

Declaration
  function IsLeaf(Cursor : TTreeCursor) : boolean;
Description
  Returns true if Cursor is pointing at an external node (a leaf).
  Note that although this implementation of binary trees uses nil for
  external nodes, this does NOT mean that a cursor that's pointing to
  an external node is itself nil or zero.

Declaration
  function IsRoot(Cursor : TTreeCursor) : boolean;
Description
  Returns true if Cursor is pointing at the data object at the tree's
  root.

Declaration
  function Iterate(Action : TIteratorFunc;
                   Backwards : boolean;
                   ExtraData : pointer) : TListCursor;
Description
  Walks the tree from the root data object in the traversal order
  defined by TraversalType. If Backwards is False the traversal goes
  from left to right, if True from right to left. Iterate calls Action
  for each data object found.  If Action returns False, then this
  method immediately returns with that data object's cursor; if Action
  always returns True then this method will return 0. ExtraData is a
  pointer to any other data that you may want Action to use.

Declaration
  procedure Join(Cursor : TTreeCursor; Tree : TBinTree); virtual;
Description
  Moves all the data objects in Tree onto the tree at the position
  pointed to by Cursor, where Cursor is assumed to be an external
  node. Tree is then disposed of. In DEBUG mode an assertion error
  will occur if Cursor is not an external node.

Declaration
  function Left(Cursor : TTreeCursor) : TTreeCursor;
Description
  Returns the cursor of the left child of Cursor. In DEBUG mode, an
  assertion error will occur if Cursor is at an external node.

Declaration
  function Parent(Cursor : TTreeCursor) : TTreeCursor;
Description
  Returns the cursor of the parent of Cursor. In DEBUG mode, an
  assertion error will occur if Cursor is pointing at the root node
  (which has no parent of course).

Declaration
  function Replace(Cursor : TTreeCursor; aData : pointer) : pointer;
Description
  Replaces the data object at the cursor with aData and returns the
  replaced data object. In DEBUG mode, an assertion error will occur
  if Cursor is an external node.

Declaration
  function Right(Cursor : TTreeCursor) : TTreeCursor;
Description
  Returns the cursor of the right child of Cursor. In DEBUG mode, an
  assertion error will occur if Cursor is at an external node.

Declaration
  function Root : TTreeCursor;
Description
  Returns the cursor of the root data object.

Declaration
  function Search(var Cursor : TTreeCursor;
                      aData  : pointer) : boolean; virtual;
Description
  Returns true if the data object aData is found in the tree (the
  tree's Compare function must return 0 between it and an object in
  the list), and returns the cursor. If aData was not found then
  Cursor is undefined.

──────────────────────────────────────────────────────────────────────

TBinSearchTree
==============

A binary search tree is a sorted binary tree where for any given data
object, all data objects in its left subtree are less than it, and all
data objects in the right subtree are greater than it. This ordering
relies on the Compare function to be overridden.

Binary search trees of this simple type suffer from the well-known
problem that they can degenerate into sorted linked lists. There is no
balancing mechanism for dealing with such degenerate cases as
inserting data objects in sorted order or in other pathological
orders.

For example insert the letters abcd into a binary search tree using
the normal ASCII collating sequence and you'd get the tree:

                     a
                      \
                       b
                        \
                         c
                          \
                           d

and if you inserted the letters aebdc into a binary search tree you'd
get:

                     a
                      \
                       e
                      /
                     b
                      \
                       d
                      /
                     c

For a balanced tree see the red-black tree TrbSearchTree. However if
you are fairly sure that either (a) the number of data objects is
likely to be small and/or (b) they will be inserted in a non-sorted
fashion, then an ordinary binary search tree will be more efficient.

Interfaced Methods
------------------

Declaration
  constructor Clone(Source : TAbstractContainer;
                    DataOwner : boolean; NewCompare : TCompareFunc);
                                                             override;
Description
  Creates a copy of the Source binary search tree.

Declaration
  function Delete(Cursor : TTreeCursor) : TTreeCursor;  virtual;
Description
  Deletes the data object at Cursor from the tree, and returns the
  cursor of the data object that replaced the deleted one. NOTE: you
  can delete any internal node in a binary search tree (the tree will
  be rearranged), but Delete will still cause an error if you try and
  delete an external node.

Declaration
  procedure Insert(var Cursor : TTreeCursor; aData : pointer);
                                                            override;
Description
  Searches for the data object with the Search method. If not found,
  Search will return an external cursor, and the data object is
  inserted there.  If found an exception will be raised with code
  edsInsertDup.  The cursor of the newly inserted data object is
  returned in Cursor.

Declaration
  procedure Join(Cursor : TTreeCursor; Tree : TBinTree); override;
Description
  Moves all the data objects in Tree into Self. Because of the
  sorted nature of binary search trees, the new data objects cannot
  be inserted en masse at Cursor: the tree must maintain its
  sequence. Hence Cursor is not used and is ignored (but must be
  defined as Join is a virtual method).

Declaration
  function Replace(Cursor : TTreeCursor;
                    aData : pointer) : pointer;
Description
  Replaces the data object of Cursor, and returns the replaced
  object. Note that this is just shorthand for Delete followed by
  Insert.

Declaration
  function Search (var Cursor : TTreeCursor;
                         aData : pointer) : boolean; virtual;
Description
  Searches for a data object aData by traversing the tree (in 'sorted'
  order), and calling the Compare method for each visited data object
  and the given data object aData. If Compare returns 0 (equal),
  Search will return the cursor of the current data object, if Compare
  never returns 0, Search returns the cursor of the external node
  where it ended up (this would be where the data object could be
  inserted).

──────────────────────────────────────────────────────────────────────

TrbSearchTree
=============

A red-black tree is a binary search tree with inbuilt tree balancing
algorithms during Insert and Delete. This ensures that the tree does
not degenerate into a sorted linked list, maintaining its excellent
search times. Balancing in this sense means that the internal
algorithms try to ensure that the path from every leaf to the root is
'about' the same, it does not ensure that they are all equal (or at
most one apart).

The tree is called red-black because certain nodes in the tree are
labelled Black and the others are labelled Red such that

   (1) all external nodes (or leaves) are Black,

   (2) every Red data object (that is not at the root) has a Black
       parent,

   (3) each path from leaf to root has the same number of Black data
       objects.

This set of rules ensures that the tree is (quite) balanced. To see
that this is so I would recommend you read [Sedgewick] or [Wood].

Interfaced Methods
------------------

Declaration
  function Delete(Cursor : TTreeCursor) : TTreeCursor; override;
Description
  Deletes the data object at Cursor from the tree, and returns the
  cursor of the data object that replaced the deleted one. Re-balances
  the tree if necessary.

Declaration
  procedure Insert(var Cursor : TTreeCursor;
                       aData : pointer); override;
Description
  Searches for the data object with Search. If found an exception
  will be raised with code edsInsertDup.  Otherwise, the data object
  is inserted at the cursor returned by Search, and the tree is
  re-balanced if necessary.  The cursor of the newly inserted data
  object is returned in Cursor.

──────────────────────────────────────────────────────────────────────

TEZCollection
=============

A collection is an array of objects. Data objects are referenced by
a zero-based element number. The collection array expands when
required to insert new data objects.

In Borland Pascal 7 (and earlier, Turbo Pascal 6) there was an object
called TCollection, but this was not transferred over to Delphi;
instead being replaced by the TList class (and its descendants).
Unfortunately there was a large group of programmers who were
migrating their applications from BP7 to Delphi, and therefore had
need of a TCollection class. They basically had two options, convert
the TCollection object to a new model TCollection class, or to write
a TCollection based on the new TList class.

The TEZCollection provides an array of data objects in the manner of
TList and TCollection. The array expands automatically when required,
up to a limit of 1 million objects (cf 16K objects for TList in Delphi
1.x and TCollection in BP7).


Notes for TCollection users
---------------------------

The TEZCollection has been incorporated into the EZDSL container
heirarchy and so operates is a slightly different way than
TCollection. The differences are noted below:

 - TEZCollection has been written to use the Delphi object model,
   specifically to use classes, exceptions and properties. For
   example: Count is now a property; the Error method no longer
   exists, it is replaced by raising specific exceptions.

 - the Delta field is not required for the algorithm within
   TEZCollection, it no longer exists.

 - Limit is now a longint and is a property.

 - Items is now an array property and the At and AtPut methods are
   no longer required, since it is easier to code an array index. So
   replace At(i) and AtPut(i) calls by Items[i]. Note that At and
   AtPut still exist for compatibility reasons.

 - the Init constructor has been replaced by the Create constructor.
   Following the EZDSL standard, this is a virtual constructor taking
   a single parameter indicating whether the collection is to be a
   data owner or not. The ALimit and ADelta parameters are not
   required by TEZCollection.

 - Load, Store, GetItem, PutItem do not exist at the moment, they
   will make an appearance in a later version of EZDSL.

 - the Done destructor is now called Destroy.

 - FirstThat, LastThat and ForEach no longer exist, they have been
   replaced by Iterate. Note also that Iterate does NOT use a nested
   Action routine, it must be global. To replace the calling routine's
   local data which is used by the nested Action routine, use the
   ExtraData pointer.

 - Pack does not delete all the nil pointers in the collection; it
   squeezes unused space from the internal array fields instead.

 - the FreeItem method has been replaced by the DisposeData property,
   like all other EZDSL classes.


Properties
----------

Declaration
  property Items[Index : longint] : pointer
Description
  An array property: the array of items in the collection. Index is
  in the range zero to Count-1, outside of this range an exception
  will be generated. Items is a default array property as well: you
  can use the collection as if it were an array without the need to
  reference the Items property explicitly.

Declaration
  property Limit : longint
Description
  READ ONLY. The maximum number of items that the collection can hold
  at the moment without further expansion.


Interfaced methods
------------------

Declaration
  constructor Create(DataOwner : boolean); override;
Description
  Creates the collection by calling the ancestor's Create after
  setting a node size of 0 (ie the collection is responsible for its
  'nodes'). If DataOwner is true, the new tree will own its data
  objects.

Declaration
  constructor Clone(Source : TAbstractContainer;
                    DataOwner : boolean; NewCompare : TCompareFunc);
                                                             override;
Description
  Creates a copy of the Source collection.

Declaration
  destructor Destroy; override;
Description
  Calls Empty, and then destroys the internal structures.

Declaration
  procedure Assign(Source : TPersistent); override;
Description
  If the Source object is a TEZCollection, empties itself with Empty,
  sets the DisposeData, DupData and CompareData properties equal to
  Source's, and then copies all of Source's data objects into itself
  (the data will be duplicated if Source is a data owner).

Declaration
  function  At(Index : longint) : pointer;
Description
  Returns the data object at Index in the collection. An exception is
  raised if Index is not in the range 0 to Count-1.

Declaration
  procedure AtDelete(Index : longint);
Description
  Deletes the item at Index in the collection, items below are moved
  up one position.  The data object is not disposed of. An exception
  is raised if Index is not in the range 0 to Count-1.

Declaration
  procedure AtFree(Index : longint);
Description
  Like AtDelete, but also disposes of the data object (providing the
  collection is a data owner).

Declaration
  procedure AtInsert(Index : longint; Item : pointer);
Description
  Inserts the data object at Index in the collection. The items at
  Index and below are moved down one position. An exception is raised
  if Index is not in the range 0 to Count (AtInsert when called with
  an Index of Count will append the item to the end of the array).
  Another exception will be raised if the collection has the maximum
  number of items already.

Declaration
  procedure AtPut(Index : longint; Item : pointer);
Description
  Replaces the data object at Index in the collection with the new
  data object Item.  An exception is raised if Index is not in the
  range 0 to Count-1.

Declaration
  procedure Delete(Item : pointer);
Description
  Deletes the data object given by Item from the collection. The data
  object is not disposed of. The routine is coded as a call to
  IndexOf, followed by a call to AtDelete providing the data object
  was found.

Declaration
  procedure DeleteAll;
Description
  Deletes all data objects from the collection; none are disposed of.
  After a call to DeleteAll the number of data objects in the
  collection will be zero.

Declaration
  procedure Free(Item : pointer);
Description
  Like Delete except that the data object will be disposed of,
  provided that the collection is a data owner. NOTE: this method will
  replace TObject.Free (the method that checks if Self is nil and if
  not calls Destroy); to call the original version, code it as
  TObject(MyCollection).Free.

Declaration
  procedure FreeAll;
Description
  Calls Empty to dispose of and delete all data objects in the
  collection.

Declaration
  function  IndexOf(Item : pointer) : longint; virtual;
Description
  Returns the index of the Item data object. If not found the routine
  returns -1. In this class, this is coded as a sequential search
  through the collection looking for a data object with the same
  pointer value as Item; sorted descendants will use a binary search
  technique using the Compare property.

Declaration
  procedure Insert(Item : pointer); virtual;
Description
  Inserts the data object into the collection. In this class the data
  object is appended to the end of the collection; sorted descendants
  will insert the data object in the correct sequence.

Declaration
  function  Iterate(Action : TIterator; Backwards : boolean;
                    ExtraData : pointer) : pointer;
Description
  Iterate through all the data objects in the collection calling
  Action for each one. If Backwards is False the iteration proceeds
  from the 0 to (Count-1), if True the iteration proceeds from
  (Count-1) to 0. If Action returns False for a data object, Iterate
  terminates immediately with the data object as the function result.
  If Action always returns True, Iterate will return nil.

Declaration
  procedure Pack;
Description
  Removes all unused space from the internal structures in the
  collection. If a collection's data remains fairly static (at least
  in terms of numbers) it might be beneficial to call Pack to reduce
  the overall amount of space used by the collection.

──────────────────────────────────────────────────────────────────────

TEZSortedCollection
===================

A sorted variant of TEZCollection. As it is sorted you must provide a
Compare routine.


Interfaced methods
------------------

Declaration
  function  IndexOf(Item : pointer) : longint; override;
Description
  Returns the index of an item: the item is searched for by using the
  fact that the collection is sorted.

Declaration
  procedure Insert(Item : pointer); override;
Description
  Inserts the item into the collection into the proper point in the
  sorted sequence as defined by the Compare routine. If the item is
  already present, an exception is raised with code edsInsertDup.

Declaration
  function  Search(Item : pointer; var Index : longint) : boolean;
                                                              virtual;
Description
  Searches for the item in the collection by using the fact that the
  collection is sorted. If found it returns true and the index of the
  item in the collection. If not found it will return false and Index
  is the index where the item would be inserted.

──────────────────────────────────────────────────────────────────────

TEZStringCollection
===================

A variant of TEZSortedCollection where the items are all strings
(short strings in Delphi 2.0). The Create constructor will set up the
DupData, Compare and DisposeData routines for you: the container can
be used as is.


Interfaced methods
------------------

Declaration
  constructor TEZStringCollection.Create(DataOwner : boolean);
Description
  Calls the ancestor's Create constructor and then sets the DupData
  property to EZStrDupData, the DisposeData property to
  EZStrDisposeData and the Compare property to EZStrCompare.

──────────────────────────────────────────────────────────────────────

TEZStrZCollection
===================

A variant of TEZSortedCollection where the items are all null-
terminated strings (aka PChars). The Create constructor will set up
the DupData, Compare and DisposeData routines for you: the container
can be used as is.


Interfaced methods
------------------

Declaration
  constructor TEZStrZCollection.Create(DataOwner : boolean);
Description
  Calls the ancestor's Create constructor and then sets the DupData
  property to EZStrZDupData, the DisposeData property to
  EZStrZDisposeData and the Compare property to EZStrZCompare.

──────────────────────────────────────────────────────────────────────


And Finally...
----------------------------------------------------------------------

..the legal bit.

I am releasing the EZDSL library and accompanying example programs,
units, source code and documentation as freeware. To remind you,
freeware means that it doesn't cost you anything, but that I retain
full and all copyright. You may include EZDSL in compiled executable
programs or DLLs with no royalty charges being levied, but you may
not distribute for monetary gain any of the source code,
documentation, example programs, or compiled units within EZDSL with
source of your own (as a programming library for example) without
first asking me and getting my approval, and without including my
copyright notice and without paying money to the charity of my choice
for the pleasure of doing so.

I also do not assume any liability whatsoever for your use or misuse
of the EZDSL unit, source code, documentation and example programs.
This code (as is ALL code) is liable to have bugs: if it's important
to you, test, test and then test again.

If you want the latest version of EZDSL you can get it officially
from two places: the TurboPower BBS (on 719 260 9726, any baud, 8N1)
and from the DELPHI forum on CompuServe. I am not interested in
supporting any other outlets, excellent though they may be.

Enjoy. If you have any problems, you can get in touch with me via
private e-mail on CompuServe on [100116,1572]. For Internet users
that's [e-mail].  Similarly, if you'd like some
extensions to it get in touch and I'll see what I can do.


Dedication
----------------------------------------------------------------------
To Joanna, I'm deeply sorry it didn't work out.


                 Julian M. Bucknall, Colorado Springs, USA, March 1996

EZDSL, the library, the units, the include files and this
documentation, is Copyright (c) 1993-1996 Julian M. Bucknall
======================================================================